package 树.BST;

/*
解题思路：
    BST问题最核心的框架就是“明确一个节点要做的事情，剩下的事情交给递归框架”
    这题中“一个节点该做的事情”就是 和low、high比较。
    如果root.val>high，证明root的右子树都比high大，裁剪掉它的右子树，然后再遍历它剩下的那颗右子树。
    如果root.val<low，证明root的左子树都比low小，裁剪掉它的左子树，然后再遍历它剩下的那颗左子树。
*/
public class 修剪二叉搜索树_669 {

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {//如果root 小于low，那么root的左子树也一定都小于low，所以把左子树都裁剪掉
            root = root.right;

            return trimBST(root, low, high);//继续遍历裁剪后的节点的右子树
        }
        if (root.val > high) {
            root = root.left;
            return trimBST(root, low, high);
        }


        // 这条线以上是明确一个节点该做的事
        /************************************************************/
        //线以下是把剩下的事抛给递归框架


        //如果目前节点的值满足范围，就去遍历它的左子树和右子树看它们是不是满足要求
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;
    }
}
